// https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/

// 题干：给你一个整数数组 arr 和一个整数 difference，
//      请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
//      子序列 是指在不改变其余元素顺序的情况下，
//      通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

// 示例：输入：arr = [1,2,3,4], difference = 1
//      输出：4

// 碎语：当出现重复查询的时候，可以考虑哈希表

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int longestSubsequence(vector<int>& arr, int difference)
    {

        int n = arr.size(), ret = 1;
        if (n == 1) return 1;

        vector<int> dp(n, 1);
        unordered_map<int, int> hash; // 哈希表存下前面出现过的可能b

        for (int i = 1 ; i < n ; i++){ // 填满所有dp表
            hash[arr[i - 1]] = i - 1; // 先存下或更新上一位置的数据
            if (hash.count(arr[i] - difference)){
                dp[i] = dp[hash[arr[i] - difference]] + 1;
            }
            ret = max(ret, dp[i]);
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> arr = {1,2,3,4};

    cout << sol.longestSubsequence(arr, 1) << endl;

    return 0;
}